package com.celan.year2023.month01.day23;

import java.util.Arrays;

public class Solution {
    public double calculateTax(int[][] brackets, int income) {
        double tax = 0;
        int pre = 0;
        for (int i = 0; i < brackets.length; i++) {
            int limit = brackets[i][0];
            int percent = brackets[i][1];
            if (income >= limit) {
                tax += (limit - pre) * percent * 0.01;
            } else {
                tax += (income - pre) * percent * 0.01;
                break;
            }
            pre = limit;
        }
        return tax;
    }

    public boolean canPartition(int[] nums) {
        int n = nums.length;
        //判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
        //若sum无法被2整除说明无法平均分为两份，直接返回false
        int sum = Arrays.stream(nums).sum();
        if (sum % 2 != 0) return false;
        int target = sum / 2;
        //转变为背包问题->容量为target的背包，放入nums中的数字，最大价值是否等于target
        int[] dp = new int[target + 1];
        for (int i = 0; i < n; i++) {
            //一维dp时，物品遍历在外层，容量遍历在内层，遍历背包需要反向遍历
            for (int j = target; j >= nums[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        return dp[target] == target;
    }

    public int lastStoneWeightII(int[] stones) {
        //先把石头分为尽量相等的两堆，最后的结果则是这两堆石头的差值
        int n = stones.length;
        int sum = Arrays.stream(stones).sum();
        int target = sum / 2;
        //转换为背包问题后，代码几乎没有改动
        //石头的value和weight都是石头的重量
        int[] dp = new int[target + 1];
        for (int i = 0; i < n; i++) {
            //一维dp时，物品遍历在外层，容量遍历在内层，遍历背包需要反向遍历
            for (int j = target; j >= stones[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }
        return sum - dp[target] * 2;
    }

    public int findTargetSumWays(int[] nums, int target) {
        int n = nums.length;
        int sum = Arrays.stream(nums).sum();
        if (target < 0 && sum < -target) return 0;
        if ((target + sum) % 2 != 0) return 0;
        int bag = (target + sum) / 2;
        if (bag < 0) bag = -bag;
        //dp[j] 表示：填满j（包括j）这么大容积的包，有dp[j]种方法
        int[] dp = new int[bag + 1];
        dp[0] = 1;
        //dp[j] += dp[j - nums[i]]
        //只要搞到nums[i]，凑成dp[j]就有dp[j - nums[i]]种方法。
        for (int i = 0; i < n; i++) {
            for (int j = bag; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[bag];
    }

    public int findMaxForm(String[] strs, int m, int n) {
        int length = strs.length;
        //dp[i][j]代表最多0有i个，1有j个，当前子集数量
        int[][] dp = new int[m + 1][n + 1];
        for (int k = 0; k < length; k++) {
            int zero = count(strs[k])[0];
            int one = count(strs[k])[1];
            for (int i = m; i >= zero; i--) {
                for (int j = n; j >= one; j--) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - zero][j - one] + 1);
                }
            }
        }
        return dp[m][n];
    }

    private int[] count(String str) {
        int zero = 0, one = 0;
        for (char c : str.toCharArray()) {
            if (c == '0') zero++;
            if (c == '1') one++;
        }
        return new int[]{zero, one};
    }

    public int change(int amount, int[] coins) {
        int n = coins.length;
        int[] dp = new int[amount + 1];
        //求方法数一般都要注意初始化
        dp[0] = 1;
        for (int i = 0; i < n; i++) {
            //完全背包从小到大遍历
            for (int j = coins[i]; j <= amount; j++) {
                //一般求方法数递推公式
                dp[j] += dp[j - coins[i]];
            }
        }
        return dp[amount];
    }

    public int combinationSum4(int[] nums, int target) {
        int n = nums.length;
        int[] dp = new int[target + 1];
        //求方法数一般都要注意初始化
        dp[0] = 1;
        //排列问题先遍历背包
        //完全背包从小到大遍历
        for (int j = 0; j <= target; j++) {
            for (int i = 0; i < n; i++) {
                if (j >= nums[i])
                    //一般求方法数递推公式
                    dp[j] += dp[j - nums[i]];
            }
        }
        return dp[target];
    }

    public int coinChange(int[] coins, int amount) {
        int n = coins.length;
        //凑成总金额所需的最少的硬币个数
        int[] dp = new int[amount + 1];
        for (int i = 1; i < dp.length; i++) {
            dp[i] = amount + 1;
        }
        for (int i = 0; i < n; i++) {
            //完全背包从小到大遍历
            for (int j = coins[i]; j <= amount; j++) {
                //一般求方法数递推公式
                dp[j] = Math.min(dp[j - coins[i]] + 1, dp[j]);
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }

    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            //完全背包从小到大遍历
            for (int j = i * i; j <= n; j++) {
                //一般求方法数递推公式
                dp[j] = Math.min(dp[j - i * i] + 1, dp[j]);
            }
        }
        return dp[n];
    }
}
